#include <iostream>
#include <stdlib.h>
#define TestNumber 100
using namespace std;

int sort(int *arr, int n);
int format(int *arr, int n);

int main(int argc, char**argv)
{
    if (argc < 2)
    {
        cout << "please input something." << endl;
        return 0;
    }

    int arr[TestNumber + 2];

    for (int i = 0; i < TestNumber; i++)
    {
        arr[i] = atoi(argv[i + 1]);
    }

    sort(arr, TestNumber);
    format(arr, TestNumber);
    return 1;
}

int format(int *arr, int n)
{
    cout << arr[0] << "/";
    cout << arr[1];
    cout << "/";
    for (int i = 0; i < TestNumber; i++)
    {
        cout << arr[i + 2] << "\t";
        if ((i + 1) % 6 == 0)
        {
            cout << "n";
        }
    }
    cout << endl;
    return 1;

}

int sort(int *arr, int n)
{

    int final = 0, first = 0, k;
    int *temp;
    temp = (int *) malloc(sizeof (temp) * n);
    temp[0] = arr[0];
    int compareCount = 0;
    int moveCount = 0;

    for (int i = 1; i < n; i++)
    {
        if (arr[i] < temp[first])
        { // 待插入元素比最小的元素小
            first = (first - 1 + n) % n;
            temp[first] = arr[i];

            moveCount++;
        }
        else if (arr[i] > temp[final])
        { // 待插入元素比最大元素大
            final = (final + 1 + n) % n;
            temp[final] = arr[i];

            moveCount++;
        }
        else
        { // 插入元素比最小大，比最大小
            k = (final + 1 + n) % n;
            moveCount++;
            while (temp[((k - 1) + n) % n] > arr[i])
            {
                temp[(k + n) % n] = temp[(k - 1 + n) % n];
                k = (k - 1 + n) % n;

                moveCount++;
                compareCount++;
            }
            temp[(k + n) % n] = arr[i];
            final = (final + 1 + n) % n;
            compareCount++;

            moveCount++;
        }
        compareCount++;
    }

    arr[0] = moveCount;
    arr[1] = compareCount;
    // 将排序记录复制到原来的顺序表里
    for (k = 0; k < n; k++)
    {
        arr[k + 2] = temp[(first + k) % n];
    }
}



